package leetcode.code0050;

import java.util.TreeMap;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution50 implements IDebug {

	public double myPow(double x, int n) {
		if (n == 0)
			return 1;
		double ans = x;
		long loop = n > 0 ? n : -(long)n;
		long cur = 1;
		long m = 0;
		TreeMap<Long, Double> tm = new TreeMap<>();
		tm.put(1l, x);
		while ((m = cur << 1) < loop) {
			ans *= ans;
			cur <<= 1;
			tm.put(m, ans);
		}
		while ((m = loop - cur) != 0) {
			Long sub = tm.floorKey(m);
			ans *= tm.get(sub);
			cur += sub;
		}
		return n > 0 ? ans : 1 / ans;
	}

	public static void main(String[] args) {
		Solution50 so = new Solution50();
//		so.debug1();
//		so.debug2();
//		so.debug3();
		so.debug4();
	}

	@Override
	public void debug1() {
		double x = 2.00000;
		int n = 10;
		double e = 1024.00000;
		double r = this.myPow(x, n);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug2() {
		double x = 2.10000;
		int n = 3;
		double e = 9.26100;
		double r = this.myPow(x, n);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug3() {
		double x = 2.00000;
		int n = -2;
		double e = 0.25000;
		double r = this.myPow(x, n);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug4() {
		double x = 1.00000;
		int n = -2147483648;
		double e = 0.25000;
		double r = this.myPow(x, n);
		HelpDebug.compare(e, r);
	}

}
